package com.jeff.practice;

import java.util.ArrayList;
import java.util.List;

public class Test5 {
    /**
     * 找出数组中缺失的数字。
     * 给定一个包含 n 个整数的数组 nums，这些整数的范围是 [1, n]，其中 nums[i] 在 [1, n] 内。
     * 此方法通过标记出现的数字，然后找出未被标记的索引+1，即为缺失的数字。
     *
     * @param nums 输入的整数数组，长度为 n，整数范围是 [1, n]。
     * @return 返回一个包含所有缺失数字的列表。
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // 获取数组长度
        int n = nums.length;

        // 遍历数组，通过数学运算将出现的数字标记在数组的相应位置
        for (int num : nums) {
            int x = (num - 1) % n;
            nums[x] += n;
        }

        // 创建一个列表用于存储缺失的数字
        List<Integer> ret = new ArrayList<>();

        // 再次遍历数组，找出未被标记的索引+1，即为缺失的数字
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.add(i + 1);
            }
        }

        // 返回包含所有缺失数字的列表
        return ret;
    }


    public static void main(String[] args) {
        int[] nums = {4, 3, 2, 7, 8, 2, 3, 1};
//        int[] nums = {1,1};
        Test5 test = new Test5();
        System.out.println(test.findDisappearedNumbers(nums));
    }
}
